#include <stdio.h>
#include <stdlib.h>

typedef int ElemType; // 自定义元素类型（可根据需求修改，如char、float等）

/**
 * 【单链表】
 * 链表节点结构体定义

 这里使用了 `typedef` 关键字同时定义了两个类型别名：

1. `LNode`：代表 `struct LNode` 结构体类型
2. `LinkList`：代表 `struct LNode *` 指针类型（注意 `*LinkList` 前面的星号）

因此：
- `LNode *list` 表示声明一个指向 `LNode` 结构体的指针变量
- `LinkList list` 由于 `LinkList` 已经被定义为 `struct LNode *` 类型，所以这也表示声明一个指向 `LNode` 结构体的指针变量

两者在语义上完全等价，都声明了一个指向链表节点的指针变量，只是写法不同。使用 `LinkList` 可以让代码更清晰地表达这是链表类型的指针。
 */
typedef struct LNode
{
  ElemType data;      // 数据域：存储元素值
  struct LNode *next; // 指针域：指向下一个节点
} LNode, *LinkList;   // LNode为节点类型，LinkList为节点指针类型，用于表示链表的头指针

// 1.1 创建链表，使用头插法
void CreateList_L(LinkList *L, int n)
{
  // 链表的头节点初始化
  *L = (LinkList)malloc(sizeof(LNode)); // 修改main函数中的L指针
  if (*L == NULL)
  {
    printf("Memory allocation failed!\n");
    return;
  }
  (*L)->next = NULL;

  printf("请输入%d个节点的数据值：\n", n);
  for (int i = 0; i < n; i++)
  {
    LNode *p = (LNode *)malloc(sizeof(LNode));
    if (p == NULL)
    {
      printf("Memory allocation failed!\n");
      return;
    }
    // printf("第%d个节点: ", i + 1);
    scanf("%d", &p->data);

    p->next = (*L)->next; // 新节点的next指向当前头节点的后继
    (*L)->next = p;       // 头节点的next指向新节点
  }
}

// 1.2 创建链表，使用尾插法
void CreateList_R(LinkList *L, int n)
{
  // 链表的头节点初始化
  *L = (LinkList)malloc(sizeof(LNode));
  if (*L == NULL)
  {
    printf("Memory allocation failed!\n");
    return;
  }
  (*L)->next = NULL;

  LNode *tail = *L; // 尾指针，指向当前链表的最后一个节点

  printf("请输入%d个节点的数据值：\n", n);
  for (int i = 0; i < n; i++)
  {
    LNode *p = (LNode *)malloc(sizeof(LNode));
    if (p == NULL)
    {
      printf("Memory allocation failed!\n");
      return;
    }
    // printf("第%d个节点: ", i + 1);
    scanf("%d", &p->data);

    tail->next = p; // 将新节点链接到链表的尾部
    tail = p;       // 更新尾指针
  }
}

// 2. 遍历链表
void TraverseList(LinkList L)
{
  LNode *p = L->next; // p指向第一个元素节点
  while (p != NULL)
  {
    printf("%d ", p->data); // 打印当前节点的元素值
    p = p->next;            // 指针后移，访问下一个节点
  }
  printf("\n");
}

// 3. 按值查找元素
LNode *LocateElem(LinkList L, ElemType e)
{
  LNode *p = L->next; // 从第一个元素节点开始遍历
  while (p != NULL && p->data != e)
  {
    p = p->next; // 未找到目标值，指针后移
  }
  return p; // 找到返回节点指针，未找到返回NULL
}

// 4. 按位置插入元素
int InsertElem(LinkList L, int pos, ElemType e)
{
  if (pos < 1)
    return 0; // 位置不合法（pos最小为1）

  LNode *p = L; // p从“头结点”开始
  int j = 0;    // 记录当前是第几个节点

  // 找到第pos-1个节点（插入位置的前驱节点）
  while (p != NULL && j < pos - 1)
  {
    p = p->next;
    j++;
  }

  if (p == NULL)
    return 0; // 位置超出链表范围

  // 为新节点分配内存并插入
  LNode *newNode = (LNode *)malloc(sizeof(LNode));
  if (newNode == NULL)
  {
    printf("Memory allocation failed!\n");
    return 0;
  }
  newNode->data = e;       // 新节点存入值
  newNode->next = p->next; // 新节点的next指向“前驱节点的原后继”
  p->next = newNode;       // 前驱节点的next指向新节点
  return 1;                // 插入成功
}

// 5.1 按位置删除节点
int DeleteElem(LinkList L, int pos, ElemType *e)
{
  if (pos < 1)
    return 0; // 位置不合法

  LNode *p = L; // p从“头结点”开始
  int j = 0;    // 记录当前是第几个节点

  // 找到第pos-1个节点（删除位置的前驱节点）
  while (p != NULL && j < pos - 1)
  {
    p = p->next;
    j++;
  }

  // 位置超出范围 或 前驱节点后无节点可删
  if (p == NULL || p->next == NULL)
    return 0;

  LNode *q = p->next; // q指向“要删除的节点”
  *e = q->data;       // 用e带回被删除节点的值
  p->next = q->next;  // 前驱节点的next指向“被删节点的后继”
  free(q);            // 释放被删节点的内存
  return 1;           // 删除成功
}

// 5.2 函数功能：删除链表中所有值为val的节点，返回新的头节点
LinkList DeleteElemByVal(LinkList L, ElemType val)
{
  // 创建哑节点，简化头节点删除的特殊情况
  LNode *dummy = (LNode *)malloc(sizeof(LNode));
  if (dummy == NULL)
  {
    // 内存分配失败，返回原链表
    return L;
  }
  dummy->next = L;        // 哑节点指向原头节点
  LNode *current = dummy; // 遍历指针从哑节点开始

  // 遍历链表，检查当前节点的下一个节点是否需要删除
  while (current->next != NULL)
  {
    if (current->next->data == val)
    {
      // 找到需要删除的节点，保存待删除节点
      LNode *temp = current->next;
      // 跳过待删除节点
      current->next = current->next->next;
      // 释放待删除节点的内存
      free(temp);
    }
    else
    {
      // 不需要删除时，指针后移
      current = current->next;
    }
  }

  // 保存新的头节点（哑节点的下一个节点）
  LNode *newHead = dummy->next;
  // 释放哑节点的内存（避免内存泄漏）
  free(dummy);
  // 返回新的头节点
  return newHead;
}

// 6. 销毁链表
void DestroyList(LinkList *L)
{
  LNode *p = *L; // p从“头结点”开始
  LNode *q;      // 临时指针，用于保存下一个节点

  while (p != NULL)
  {
    q = p->next; // 保存下一个节点的地址
    free(p);     // 释放当前节点
    p = q;       // 指针后移，处理下一个节点
  }
  *L = NULL; // 头指针置空，防止野指针
}

// 7.1 合并有序链表
void MergeSortedLists(LinkList *La, LinkList *Lb, LinkList *Lc)
{
  LinkList pa = (*La)->next; // 指向La的第一个元素
  LinkList pb = (*Lb)->next; // 指向Lb的第一个元素
  LinkList pc;               // 用于构建链表
  *Lc = pc = *La;            // 将 Lc 的头指针指向 La 的头节点

  // 合并两个有序链表
  while (pa && pb)
  {
    if (pa->data <= pb->data)
    {
      pc->next = pa;
      pc = pa;
      pa = pa->next;
    }
    else
    {
      pc->next = pb;
      pc = pb;
      pb = pb->next;
    }
  }

  // 如果 pa 不为 NULL，将剩余的节点连接到新链表的尾部
  pc->next = pa ? pa : pb;
  free(*Lb); // 释放Lb的内存，因为我们只用到了La的内存
}

// 7.2 合并有序链表（改进版 - 不影响原始链表）
void MergeSortedLists2(LinkList *La, LinkList *Lb, LinkList *Lc)
{
  LinkList pa = (*La)->next; // 指向La的第一个元素
  LinkList pb = (*Lb)->next; // 指向Lb的第一个元素

  // 为Lc创建新的头节点
  *Lc = (LinkList)malloc(sizeof(LNode));
  if (*Lc == NULL)
  {
    printf("Memory allocation failed!\n");
    return;
  }
  (*Lc)->next = NULL;

  LinkList pc = *Lc; // 用于构建链表

  // 合并两个有序链表
  while (pa && pb)
  {
    if (pa->data <= pb->data)
    {
      // 创建新节点复制pa的数据
      LinkList newNode = (LinkList)malloc(sizeof(LNode));
      newNode->data = pa->data;
      newNode->next = NULL;

      pc->next = newNode;
      pc = newNode;
      pa = pa->next;
    }
    else
    {
      // 创建新节点复制pb的数据
      LinkList newNode = (LinkList)malloc(sizeof(LNode));
      newNode->data = pb->data;
      newNode->next = NULL;

      pc->next = newNode;
      pc = newNode;
      pb = pb->next;
    }
  }

  // 处理剩余节点
  while (pa)
  {
    LinkList newNode = (LinkList)malloc(sizeof(LNode));
    newNode->data = pa->data;
    newNode->next = NULL;

    pc->next = newNode;
    pc = newNode;
    pa = pa->next;
  }

  while (pb)
  {
    LinkList newNode = (LinkList)malloc(sizeof(LNode));
    newNode->data = pb->data;
    newNode->next = NULL;

    pc->next = newNode;
    pc = newNode;
    pb = pb->next;
  }

  // 释放原来的Lb头节点
  free(*Lb);
  *Lb = NULL;
}

// 8. 反转链表
void ReverseList(LinkList *L)
{
  if (*L == NULL || (*L)->next == NULL)
    return; // 空链表或只有一个节点，无需反转

  LNode *prev = NULL;
  LNode *curr = *L;
  LNode *next = NULL;

  while (curr != NULL)
  {
    next = curr->next; // 保存下一个节点
    curr->next = prev; // 反转当前节点的指针
    prev = curr;       // 移动prev和curr指针
    curr = next;
  }
  *L = prev; // 更新头指针
}

int main()
{
  LinkList L, L2, L3; // L是链表头指针
  int n, pos, e;

  // ---------- 测试：创建链表 ----------
  printf("请输入要创建的链表节点个数：");
  scanf("%d", &n);
  CreateList_L(&L, n);  // 传递L的地址，以便函数内能修改L本身
  CreateList_L(&L2, n); // 传递L2的地址，以便函数内能修改L2本身

  printf("创建的链表 L（头插法）：");
  TraverseList(L);
  printf("创建的链表 L2（头插法）：");
  TraverseList(L2);

  // ---------- 测试：合并链表 ----------
  MergeSortedLists(&L, &L2, &L3);
  printf("合并后的链表：");
  TraverseList(L3);

  // ---------- 测试：查找元素 ----------
  printf("请输入要查找的元素：");
  scanf("%d", &e);
  LNode *find = LocateElem(L3, e);
  if (find != NULL)
  {
    printf("找到元素%d，地址为%p\n", find->data, find);
  }
  else
  {
    printf("未找到元素%d\n", e);
  }

  // ---------- 测试：插入元素 ----------
  printf("请输入要插入的位置和元素（格式：位置 元素）：");
  scanf("%d %d", &pos, &e);
  printf("插入前链表：");
  TraverseList(L3);
  if (InsertElem(L3, pos, e))
  {
    printf("插入后链表：");
    TraverseList(L3);
  }
  else
  {
    printf("插入失败\n");
  }

  // ---------- 新增测试：删除指定位置元素 ----------
  printf("请输入要删除的位置：");
  scanf("%d", &pos);
  printf("删除前链表：");
  TraverseList(L3);
  if (DeleteElem(L3, pos, &e))
  {
    printf("删除的元素是%d，删除后链表：", e);
    TraverseList(L3);
  }
  else
  {
    printf("删除失败\n");
  }

  // ---------- 新增测试：按值删除元素 ----------
  printf("请输入要按值删除的元素：");
  scanf("%d", &e);
  printf("按值删除前链表：");
  TraverseList(L3);
  // 接收返回的新的头节点
  // L3 = DeleteElemByVal(L3, e);
  LinkList newHead = DeleteElemByVal(L3, e);
  printf("按值删除后链表：");
  TraverseList(L3);
  // 直接打印头节点信息
  printf("按值删除后链表的头节点信息：\n");
  printf("  头节点地址：%p\n", (void *)newHead);
  if (newHead != NULL)
  {
    printf("  头节点data字段值：%d\n", newHead->data);
    printf("  头节点next指针：%p\n", (void *)newHead->next);

    // 如果你想看第一个数据节点的信息
    if (newHead->next != NULL)
    {
      printf("  第一个数据节点地址：%p\n", (void *)newHead->next);
      printf("  第一个数据节点data字段值：%d\n", newHead->next->data);
    }
  }

  // ---------- 新增测试：反转链表 ----------
  // printf("反转前链表：");
  // TraverseList(L3);
  // ReverseList(&L3);
  // printf("反转后链表：");
  // TraverseList(L3);

  // ---------- 测试：销毁链表 ----------
  DestroyList(&L3);
  if (L3 == NULL)
  {
    printf("链表已销毁\n");
  }

  return 0;
}